package com.wu.findgreatestsumofsubarray;

/**
 * 连续子数组的最大和
 *
 * @author lynn
 * @date 2020/8/1 - 23:39
 */
public class Solution {
    public static int FindGreatestSumOfSubArray(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        //方案一：
       /* int[] dp = new int[array.length + 1];

        dp[0] = 0;
        int res = array[0];
        for (int i = 1; i <= array.length; i++) {
            dp[i] = Math.max(array[i - 1], dp[i - 1] + array[i - 1]);
            res = Math.max(res, dp[i]);
        }
        return res;*/
        //方案二：

        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            array[i] += array[i - 1] > 0 ? array[i - 1] : 0;
            max = Math.max(max, array[i]);
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, -3, -2, 7, -15, 1, 2, 2};
        int i = FindGreatestSumOfSubArray(arr);
        System.out.println(i);
    }
}
